package leetcode;

import java.util.HashMap;

public class UnSortedArraySum {

	public int maxLength(int[] arr, int k){
		if(arr == null || arr.length <= 0){
			return 0;
		}
		//map的key表示最左边开始累加的过程中出现的sum值
		//value为sum值最早出现的位置
		HashMap<Integer, Integer> map = new HashMap<>();
		//这一步很重要，为什么呢？是什么意思呢？
		//因为一个数都不添加和肯定为0，如果不加入这一步，那么就会漏掉从数组中下标为0的子数组
		//为什么会漏掉呢？因为去查找0的时候发现没有记录，所以会漏掉
		map.put(0, -1);
		int sum = 0;	//表示从0位置开始一直到i位置所有元素的和
		int len = 0;	//表示累加和为k的最长子数组长度
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
			if(!map.containsKey(sum)){
				map.put(sum, i);
			}
		}
		sum = 0;
		for (int i = 0; i < arr.length; i++) {
			//从0...i的累加和为sum 
			sum += arr[i];
			//如果找到0...j的累加和为sum - k
			//那么[j + 1...i]的累加和自然而然就是k了
			if(map.containsKey(sum - k)){
				len = Math.max(len, i - map.get(sum - k));
			}
		}
		return len;
	}
}
